package evaluation;

/**
 * 链表荷兰国旗问题 可以通过新建一个node[]数组，通过Partition给数组排好序，然后串联整个数组解决问题，也可以通过以下解法解决问题
 */
public class LinkPartition {

    public static void main(String[] args) {
        Node head = new Node(8);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(9);
        Node node5 = new Node(2);
        Node node6 = new Node(3);

        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);

        Node node = listPartition(head, 3);
        while (node!= null){
            System.out.println(node.Data);
            node = node.Next;
        }
    }
    static class Node {
        private int Data;// 数据域
        private Node Next;// 指针域
        public Node(int Data) {
            // super();
            this.Data = Data;
        }
        public int getData() {
            return Data;
        }
        public void setData(int Data) {
            this.Data = Data;
        }

        public Node getNext() {
            return Next;
        }
        public void setNext(Node Next) {
            this.Next = Next;
        }
    }

    public static Node listPartition(Node head,int pivot){
        Node sH = null;
        Node sT = null;
        Node eH = null;
        Node eT = null;
        Node mH = null;
        Node mT = null;
        Node next = null;
        while (head!=null){
            next = head.Next;
            head.Next = null;
            if (head.Data < pivot){
                if (sH == null){
                    sH = head;
                    sT = head;
                }else {
                    sT.Next = head;
                    sT= head;
                }
            }else if (head.Data == pivot){
                if (eH == null){
                    eH = head;
                    eT = head;
                }else {
                    eT.Next = head;
                    eT= head;
                }
            }else {
                if (mH == null){
                    mH = head;
                    mT = head;
                }else {
                    mT.Next = head;
                    mT= head;
                }
            }
            head = next;
        }

        if (sT !=null){
            sT.Next = eH;
            eT = eT == null ? sT : eT;
        }
        if (eT != null){
            eT.Next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }

}
